package leetcode.editor.cn;

//给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。
//
// 如果 s 中存在多个符合条件的子字符串，返回任意一个。
//
//
//
// 注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
//
//
//
// 示例 1：
//
//
//输入：s = "ADOBECODEBANC", t = "ABC"
//输出："BANC"
//解释：最短子字符串 "BANC" 包含了字符串 t 的所有字符 'A'、'B'、'C'
//
// 示例 2：
//
//
//输入：s = "a", t = "a"
//输出："a"
//
//
// 示例 3：
//
//
//输入：s = "a", t = "aa"
//输出：""
//解释：t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。
//
//
//
// 提示：
//
//
// 1 <= s.length, t.length <= 10⁵
// s 和 t 由英文字母组成
//
//
//
//
// 进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？
//
//
//
//
// 注意：本题与主站 76 题相似（本题答案不唯一）：https://leetcode-cn.com/problems/minimum-window-
//substring/
//
// Related Topics 哈希表 字符串 滑动窗口 👍 131 👎 0

import java.util.HashMap;
import java.util.Map;

//Java：最小覆盖子串
public class M1oyTv {


    public static void main(String[] args) {
        Solution solution = new M1oyTv().new Solution();
        solution.minWindow("a", "a");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 弹性滑动窗口
         * @param s
         * @param t
         * @return
         */
        public String minWindow(String s, String t) {
            String minstr = "";
            if (s.length() < t.length()) {
                return minstr;
            }
            //统计t的字符频率
            Map<Character, Integer> map1 = getCharacterIntegerMap(t);
            HashMap<Character, Integer> map = new HashMap<>();
            int minlength = Integer.MAX_VALUE;
            int left = 0;
            int right = -1;
            while (right < s.length()-1 && left <=  s.length()-1) {
                right++;
                char c2 = s.charAt(right);
                map.put(c2, map.getOrDefault(c2, 0) + 1);
                while (containstr(map, map1) && left <= right) {//如果右指针包含，则继续移动左指针，直到不包含为止
                    //计算当前最小的长度
                    int len = right - left + 1;
                    if (len < minlength) {
                        minlength = len;
                        minstr = s.substring(left, right + 1);
                    }
                    char c = s.charAt(left);
                    map.put(c, map.get(c) - 1);
                    left++;
                }

            }
            return minstr;
        }

        //统计t的字符频率
        private Map<Character, Integer> getCharacterIntegerMap(String t) {
            Map<Character, Integer> map1 = new HashMap<>();
            char[] charArray1 = t.toCharArray();
            for (char c : charArray1) {
                map1.put(c, map1.getOrDefault(c, 0) + 1);
            }
            return map1;
        }


        /**
         * 判断是否包含，采用的时map，计算每个字符的频率
         *
         * @return
         */
        private boolean containstr(Map<Character, Integer> map, Map<Character, Integer> map1) {
            //比较
            for (Character character : map1.keySet()) {
                if (map.containsKey(character)) {
                    if (map.get(character) < map1.get(character)) {
                        return false;
                    }
                } else {
                    return false;
                }
            }
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
